package leetcode_61_80;

public class mySqrt_69 {
    /**
     * 给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
     * 由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
     * 注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
     * @param x
     * @return
     */
    public int mySqrt(int x) {
        String s = String.valueOf(x);
        StringBuilder min=new StringBuilder("1");
        StringBuilder max=new StringBuilder();
        for (int i =0;i<(s.length()+1)/2-1;i++)             //n位数乘n位数结果只有2n-1位和2n位数两种情况
            min.append("0");
        max.append(min).append("0");
        int start=Integer.valueOf(min.toString());
        int end=Integer.valueOf(max.toString());
        for (int i = start; i <= end; i++) {
            Long a = (long) (i + 1) * (i + 1);
            if (i * i <= x && a > x)
                return i;
        }
        return x;
    }


    /**
     * 二分查找
     * x 平方根的整数部分 ans 是满足 k^2 ≤ x的最大 k 值
     * 因此我们可以对 k 进行二分查找
     *1ms 99%
     * @param x
     * @return
     */
    public int mySqrt2(int x) {
        int l = 0, r = x, ans = -1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if ((long) mid * mid <= x) {
                ans = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return ans;
    }
}
